Modern computers use a virtual addressing scheme which allows the computer to address an address space larger than its internal memory. Before memory can be accessed in such a scheme, however, each virtual address must be translated to a physical address. Unfortunately, the translation process ordinarily requires multiple accesses to page and segment tables in the computer's memory, which significantly degrades the computer's performance.
To overcome this problem, a translation lookaside buffer (TLB) is used to maintain the most recently used virtual address to physical address mappings. Each TLB entry ordinarily contains a virtual address, a physical address mapped to the virtual address, and control information such as access protection and validity flags. Before translating an input virtual address in the conventional manner, the TLB is searched to see if a physical address mapping for the virtual address is present. If a physical address mapping is present in the TLB, the physical address may be obtained directly from the TLB, thus avoiding the time-wasting translation process.
TLBs can be classified into one of three different categories depending on how they store and search for virtual addresses: direct mapped, set associative, or fully associative. A direct mapped TLB maps each virtual address to a specific location in the TLB. Since there are more virtual addresses than entries in the TLB, a subset of bits of each virtual address is used to hash the virtual address to a TLB entry. Thus, each TLB entry is mapped to by more than one virtual page.
Directly mapping a TLB is the simplest and quickest method of implementing a TLB. However, when memory references to different virtual pages are accessed alternately in run time and are mapped to the same TLB location, each reference causes a TLB miss which causes the TLB to replace the entry just replaced. Since TLB misses occur regularly in a case such as this, the TLB can slow down execution of a program more than it speeds it up causing what is often referred to as thrashing.
A set associative TLB can be looked at as two or more TLBs connected in parallel with each other. Each virtual memory location corresponds to a particular line in each parallel TLB. Thus, each virtual memory location maps to more than one location in a set associative TLB, and a particular location in the TLB holds a number of virtual address mappings equal to the number of "sets" of the TLB, i.e., a four-way set associative TLB holds four virtual address to physical address mappings in each TLB address location. For a set associative TLB, the entry chosen as a replacement in instances of a TLB miss can be a function of the last entry used that is mapped to the particular address in the parallel TLBs. Set associative TLBs greatly reduce the likelihood of thrashing.
A fully associative TLB uses a content addressable memory to store virtual addresses and simultaneously compares an input virtual address to each stored virtual address. Fully associative TLBs are least likely to be effected by thrashing, however, content addressable memories are slower and take up more chip real estate for a given sized TLB than either direct mapped or set associative TLBs.
There is a large market for high-performance computers that run various types of applications efficiently. These applications can vary from super-computing scale problems, which process large amounts of data, to simpler, more ordinary applications that are not data intensive.
Applications that work with large data sets, referred to as high-end applications, consume large amounts of virtual and physical memory. If memory is divided into small pages (such as 4K byte pages), these applications require many pages and a corresponding entry for each page in the TLB. Often the number of pages required by a high-end application exceeds the number of entries in the TLB. This leads to inefficient computer operation and poor performance. Thus, for high-end applications, it is advantageous to divide memory into larger page sizes.
For other applications, which are not data intensive, however, a large page size results in inefficient operation and poor performance. For example, for a program only requiring 4K bytes of memory, a large amount of memory will be wasted if the memory is divided into 1M byte pages. Thus, for some applications, computer resources can be allocated more efficiently with a small page size. Accordingly, it is advantageous to have a TLB that can support multiple page sizes, allowing certain high-end applications to work with large pages and other applications to work with smaller pages.
Several computer manufacturers have developed prior art TLBs that support multiple page sizes. However, all of these designs incorporate either fully associative TLBs that are larger and slower for a given size than set associative TLBs, or use two separate TLBs--a main TLB for a standard sized pages and a second, block TLB for larger sized pages.